/****************************************************************************
 * Copyright (C) 2009-2010 SciTouch LLC
 * 
 * This file is part of Indigo toolkit.
 * 
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 3 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 * 
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 ***************************************************************************/

#ifndef __scaffold_detection_h_
#define __scaffold_detection_h_
#include "graph/max_common_subgraph.h"

class ScaffoldDetection {
public:
   ScaffoldDetection (const ObjArray<Graph>* graph_set);
   //two main methods for extracting scaffolds
   //extracting exact scaffold from graphs set
   void extractExactScaffold (Graph& scaffold) {_searchScaffold(scaffold, false); }
   //extracting approximate scaffold from graphs set
   void extractApproximateScaffold(Graph& scaffold){_searchScaffold(scaffold, true); }

   //array for keeping graphs for searching scaffold
   //PtrArray<Graph> graphSet;

   //callbacks for edge and vertices comparsions for input graphs
   bool (*cbEdgeWeight) (const Graph &graph1, const Graph &graph2, int i, int j, void *userdata);
   bool (*cbVerticesColor) (const Graph &graph1, const Graph &graph2, const int *core_sub, int i, int j, void *userdata);
   int (*cbSortSolutions) (const Graph &graph1, const Graph &graph2, const void *userdata);
   void *userdata;

   int (*cbEmbedding) (const int *sub_vert_map, const int *sub_edge_map, const void* info, void* userdata);
   void *embeddingUserdata;

   const ObjArray<Graph>* searchStructures;
   ObjArray<Graph>* basketStructures;

   DEF_ERROR("Scaffold detection");

public:
   //class for keeping graphs
   class GraphBasket {
   public:
      //max number of graphs to keep
      enum {
         MAX_MOLECULES_NUMBER = 100,
         NEXT_SOLUTION_SIZE_SUM = 100
      };
      GraphBasket();
      virtual ~GraphBasket();

      //initializes graphs basket
      void initBasket(const ObjArray<Graph>* graph_set, ObjArray<Graph>* basket_set, int max_number);
      //returns index of first graph in basket
      int graphBegin();
      //returns next index of graph after input index 
      int graphNext(int i);
      //checks if queue's graphs already exsist in basket. add this graphs in case false result
      void checkAddedGraphs();
      //remove graph form basket
      virtual void removeGraph(int index);
      //returns ptr of graph in basket with index
      virtual const Graph& getGraph(int index) const;
      //adds new graph to queue and returns ptr of that
      virtual Graph& pickOutNextGraph();
      //returns index of graph in basket that has maximum number of edges
      virtual int getMaxGraphIndex();
      //this method adds graph from set (defines with edges and vertices lists) to basket queue 
      virtual void addToNextEmptySpot(const Graph& graph, Array<int> &v_list, Array<int> &e_list);

      virtual const Graph& getGraphFromSet(int idx) const {return _searchStructures->at(_orderArray[idx]); }
      virtual int getGraphSetSize() const {return _graphSetSize; }

      int (*cbSortSolutions) (const Graph &graph1, const Graph &graph2, const void *userdata);
      bool (*cbMatchEdges) (const Graph &graph1, const Graph &graph2, int i, int j, void *userdata);
      bool (*cbMatchVertices) (const Graph &graph1, const Graph &graph2, const int *core_sub, int i, int j, void *userdata);
      void *userdata;


      DEF_ERROR("Graph basket");

   protected:

      
      //iterator for looking next empty graphs in set
      Dbitset _directIterator;
      //reverse iterator for looking next not empty graphs in set
      Dbitset _reverseIterator;

      const ObjArray<Graph>* _searchStructures;
      ObjArray<Graph>* _basketStructures;

      virtual void _sortGraphsInSet();

      //array for keeping indexes of sorted graphs in set
      Array<int> _orderArray;

      int _graphSetSize;

      //function for sortMoleculesInSet() method
      static int _compareEdgeCount(const int &i1,const int &i2,const void* context);

      static int _copmpareRingsCount(const Graph& g1, const Graph& g2, const void* context);
      

   private:
      GraphBasket(const GraphBasket&); //no implicit copy
   };


protected:
   //method for extracting exact scaffold from graph set
   void _searchExactScaffold(GraphBasket& basket);
   //method for extracting approximate scaffold from graph set
   void _searchApproximateScaffold(GraphBasket& basket);
private:
   void _searchScaffold(Graph& scaffold, bool approximate);
};


#endif
